#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;


class Solution {
public:
    vector<string> letterCombinations(string digits) {
        unordered_map<char, vector<char>> table;

        table['2'] = vector<char>{'a', 'b', 'c'};
        table['3'] = vector<char>{'d', 'e', 'f'};
        table['4'] = vector<char>{'g', 'h', 'i'};
        table['5'] = vector<char>{'j', 'k', 'l'};
        table['6'] = vector<char>{'m', 'n', 'o'};
        table['7'] = vector<char>{'p', 'q', 'r', 's'};
        table['8'] = vector<char>{'t', 'u', 'v'};
        table['9'] = vector<char>{'w', 'x', 'y', 'z'};

        return helper(digits, table, 0);
    }

    vector<string> helper(string& digits, unordered_map<char, vector<char>>& table, int i) {
        vector<string> res;

        if (i == digits.length()) return res;
        if (i == digits.length()-1) {
            for (char c : table[digits[i]]) res.emplace_back(c+string());
            return res;
        }

        vector<string> next = helper(digits, table, i+1);
        for (char c : table[digits[i]]) {
            for (string s: next) res.emplace_back(c + s);
        }

        return res;
    }
};
